Computer operating systems often allow application programs to install "patches" within the operating system code. As used herein, a "patch" is computer code which replaces or augments a function already implemented on the computer. Typically multiple patches may be installed thereby further enhancing the original function.
When a patch replaces a function, any client calls made to the given function are transparently (from the client's perspective) redirected to the patch. The patch, in turn, performs the requested service and, if necessary, returns any results of the call to the client. In a similar manner, when a patch augments a given function, any client calls made to the given function are redirected to the patch. The patch then performs any preprocessing and passes the call along to the given function. The given function will return results directly to the client, or return results to the patch. If desired, the patch may perform post-processing and, if necessary, return the results of the call to the client.
The prototypical patch function must have the same parameters as the given function which it patches and may perform both pre-processing and post-processing. In order to further elaborate, two versions of pseudo-code for a prototypical patch function will now be provided. As will be appreciated by those skilled in the art of computer programming, the following pseudo-code provides a rough outline for use in programming a typical patch function.
The first pseudo-code is suitable for use on a computer system implementing register calling conventions:
______________________________________ typedef ResultType(TheProcType) (Param1Type param1,...); ResultType MyPatch (Param1Type param1,...1) Param1Type innerParam1; ... ResultType innerResult, finalResult; DoPrefixStuff; //This is the "head patch" part// innerResult = (*(TheProcType)NextPatch) (innerParam1,...); DoPostfixStuff, //This is the "tail patch" part//; return finalResult; } ______________________________________
The second pseudo-code is suitable for use on a computer system implementing stack calling conventions:
__________________________________________________________________________ typedef ResultType(TheProcType) (int state, Param1Type param1,...); ResuItType MyPatch (int state, Param1Type param1,...) Param1Type innerParam1; ... ResuItType innerResult, finalResult; DoPrefixStuff; //This is the "head patch" part// innerResult = (*(TheProcType)NextPatch) (state, innerParam1,...); DoPostfixStuff; //This is the "tail patch" part//; return finalResult; } __________________________________________________________________________
With reference to FIG. 2, the well known 68K patching paradigm 100 will be described. By way of background, the 68K patching paradigm 100 is implemented by versions of the Macintosh.RTM. Operating system designed for the Motorola 68K series of microprocessors, which operating system is hereinafter referred to as the "68K operating system." The paradigm 100 is implemented on a computer system such as computer system 50 of FIG. 1, wherein a CPU 52 includes one of the Motorola 68K series microprocessors or microcontrollers as well as other components necessary to properly interface with and control other devices coupled with the CPU 52.
The system routines for the 68K operating system reside mainly in ROM. However, to provide flexibility for any subsequent development, application code written for execution within the 68K operating system must be kept free of any specific ROM addresses. For this reason, all calls to system routines are passed indirectly through a trap table resident in RAM. This indirect mechanism permits the ROM addressing of system routines to vary, or to be replaced by patch routines, without affecting the operation of applications which utilize the system routines.
The 68K patching paradigm 100 includes application code 102 having at least one ATRAP instruction 104, low memory locations 106, a trap dispatcher 108, a trap table 110, ROM 120 having system code 122, and RAM 130 including at least one patch code 132. While the operating system routines reside mainly in ROM 120 (in the original state), information regarding the locations of the operating system routines is encoded in compressed form within ROM 120. Upon system start up, this information is decompressed and the trap table 110 is formed in RAM 130.
The indirect calling mechanism of the 68K patching paradigm 100 is further implemented by utilizing a feature of the 68K series microprocessor called a trap. A "trap" is a kind of microprocessor exception which arises in response to the execution of certain machine language instructions. An "exception" is an error or abnormal condition detected by the processor during the course of execution. For example, any 68K machine language instruction whose first four bits has the hexadecimal value "A" will generate an exception (hence the name "ATRAP"). In the 68K operating system, the set of language instructions whose first four bits has the hexadecimal value "A" are specifically set aside by the operating system for use in implementing client calls to system routines.
During execution of application code 102, the 68K microprocessor will encounter and execute the ATRAP 104. In response, the microprocessor pushes some state onto the computer system's stack, the state including the address of the ATRAP instruction 104. Then, the microprocessor resumes execution at the address indicated in a low memory location, which is the address of the trap dispatcher 108. Once executing, the trap dispatcher 108 examines the bit pattern of the ATRAP instruction 104 to determine what operation it stands for, looks up the address of the corresponding system routine in the trap table 110, and then jumps to the corresponding system routine.
One example of the general execution path of a system routine which is not patched is symbolized by flow control lines 140, 142, 144, 146, and 148. Note that in certain cases the flow control lines may imply structure. For example, the flow control line 146 has its tail at address.sub.-- 1 in trap table 110 and its head at the beginning of the system routine within the system code 120: right to where address.sub.-- 1 points. However, the flow control lines in general are not intended to illustrate structure.
Flow control line 140 symbolizes the microprocessor pushing the address of the ATRAP instruction 104 onto the computer system's stack and beginning execution at the trap dispatcher 108. Flow control line 142 symbolizes the trap dispatcher 108 evaluating the ATRAP instruction 104 and flow control line 144 symbolizes the trap dispatcher looking up the corresponding system routine in the trap table 110. Flow control line 146 symbolizes jumping to a system routine 123 to which address.sub.-- 1 points and flow control line 148 symbolizes jumping back to the application code 102 once the system routine 123 has been executed.
Because the trap table 110 is resident in RAM 130, individual entries in the trap table 110 can be changed to point to addresses other than the original ROM addresses. This allows the system routines to be replaced or augmented by patches. At startup time the system can load new versions of individual routines (e.g. from the System file or from a floppy disk) into RAM and then patch the trap table in order to redirect any calls to the original system routine to the new versions. Additionally, when new applications are launched they too can load new versions of individual routines into RAM and then patch the trap table in order to redirect any calls to the original system routine to the new versions.
One example of a redirection to a patched system routine is symbolized in FIG. 2 by dashed flow control lines 150 and 152. Similar to the unpatched system routine described previously, an ATRAP instruction 104 calling a patched system routine will initiate a process in which the trap dispatcher 108 will look up the system routine corresponding to the ATRAP instruction 104. However, in the patched case, address.sub.-- 1 will point to patch code 132 located in RAM 130 rather than the original system routine. Thus dashed flow control line 150 illustrates jumping to the patch code 132 and dashed flow control line 152 illustrates jumping back to the application code 102 after the patch code 132 has finished executing.
Next, in reference to FIG. 3, one method for installing patches in the 68K operating system will be described. In an initial step 200, the computer boot process is started. Then, in a step 202, the ROM boot is performed. In ROM boot step 202, initialization procedures such as expanding the trap table from ROM into RAM are performed. Next, in a step 204, the disk operating system boot is performed. At this point any system patches are also installed.
As discussed previously, new versions of individual system routines may be loaded into RAM and the trap table patched in order to redirect any calls to the original system routine to the new versions. After this is complete, the operating system boot procedure is complete in a step 206. In a next step 208, the application "Finder" is launched. As will be appreciated by those skilled in the art, the Finder is the primal application which performs critical tasks such as displaying the Macintosh.RTM. desktop and launching other applications at the request of the user. Once the Finder is running, in a step 210 other applications may be launched and in turn any patches necessary for the other applications may be installed.
Turning now to FIG. 4, the well known PowerPC patching paradigm 300 will be described. By way of background, the PowerPC patching paradigm 300 is implemented by versions of the Macintosh.RTM. Operating system designed for the PowerPC series of microprocessors, which operating system is hereinafter referred to as the "PowerPC operating system." The paradigm 300 is implemented on a computer system such as computer system 50 of FIG. 1, wherein the CPU 52 includes one of the PowerPC series microprocessors as well as other components necessary to properly interface with and control the other devices.
The example PowerPC patching paradigm 300 includes a native PowerPC application 302, an emulated segment 304, an interface library 306, a native PowerPC system routine 308, and a routine descriptor 310. In the PowerPC native environment, a "fragment" is a block of executable PowerPC code and its associated data. As illustrated, the native PowerPC application 302 is a fragment having application code 320 and application data 322.
In the native PowerPC environment, rather than directly calling system routines, application code will have a call 324 to service glue 326. As will be appreciated by those skilled in the art, service glue 326 provides an indirection across dynamically linked library boundaries. The main function of the service glue is to save memory resources. That is, if the system routine were called more than once, the service glue 326 plus the multiple calls require less memory than duplicating service glue 326 in multiple locations. The service glue in turn uses a pointer 328 found in the application data 322 which points to the transition vector 330 of the interface library 306.
In explanation, a transition vector such as transition vector 330 is a data structure which has two pointers: a code pointer (which is the address of the code of the fragment being called) and a global pointer (which is the address of the called fragment's table of contents). A fragment's "table of contents" is a table containing a pointer to each routine or data item that is imported from some other fragment, as well as pointers to the fragment's own static data.
The interface library 306 is a fragment including interface library code 332 and interface library data 334. The interface library 306 serves a function similar to the trap dispatcher 108 of FIG. 2, as is described in the following. When the service glue 326 is called to execute a system routine, the interface library code 332 is invoked via the interface transition vector 330. Then the interface library 306 evaluates the call using a trap table 340 to determine the appropriate system routine to jump to. The trap table 340 is used in a manner similar to the trap table 110 of FIG. 2.
The appropriate system routine as determined by the interface library 306 may be written in 68K type code such as 68K code 344 or may be in native PowerPC code (i.e. dynamically linked library type code). In the case of 68K code, execution jumps directly from the trap table 340 to the 68K code 344. In the case of native PowerPC code, execution jumps first to a routine descriptor 310. As used herein, a "routine descriptor" is a data structure which contains mode information necessary for the operating system to properly execute the code. By way of explanation, the PowerPC operating system has an emulator which allows 68K code to be properly executed. In the case of 68K code, execution proceeds via the trap table 340, a mixed-mode manager, and an emulator to interpret and execute the 68K code 344. The routine descriptor is one component of this mechanism.
Patching in the PowerPC patching paradigm 300 is performed in a manner similar to the 68K patching paradigm 100 of FIG. 2. That is, a patch is added by changing an element in the trap table 340 to redirect any system calls to patch code residing in RAM. Thus the PowerPC patching paradigm 300 functions by emulating the appropriate elements of the 68K patching paradigm 100 of FIG. 2.
While the prior art patching systems provide the basic capability of patching system routines, these paradigms are neither resource efficient nor do they provide the flexibility and functionality required by modern computer systems. Each of the prior art patching paradigms result in costly (in terms of system resource utilization) system exceptions every time a system routine is called. For example, each ATRAP instruction executed generates a costly exception.
A further limitation of prior art patching paradigms is that only distinguished system routines (i.e. system routines called indirectly through the trap table) may be patched. Another limitation of prior art patching paradigms is that chaining of patches (i.e. multiple patches for a system routine) must be done manually. That is, each new patch must "capture" the preceding routine and manually chain through. Furthermore, the prior schemes do not allow patches to be inserted in or deleted from a patch chain, rather they can only be appended.